package com.lwg.datastructure.CommonSelectMethod;

/**
 * @author: lwg
 * @Date: 2022/4/24 15:42
 * @Description: 插值查找
 * 描述：和二分查找类似，不同的是插值查找的mid公式为
 * left+(((key-arr[left])/(arr[right]-arr[left]))*(right-left))
 */
public class InsertSearch {
    
    public static void main(String[] args) {
        int[] arr = {1, 1};
        System.out.println(insertSearch(arr, 1, 0, arr.length - 1));
    }
    
    private static int insertSearch(int[] arr, int key, int left, int right) {
        if (left > right) {
            return -1;
        }
        if (arr[left] == arr[right]) {
            if (arr[left] == key) {
                return left;
            } else {
                return -1;
            }
        }
        
        int mid = left + (((key - arr[left]) / (arr[right] - arr[left])) * (right - left));
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] > key) {
            return insertSearch(arr, key, 0, mid - 1);
        }
        return insertSearch(arr, key, mid + 1, right);
    }
}
